package linklist;

import org.junit.Test;

import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @author kunkun
 * @className LeetCode_23
 * @Description 合并k个上升的链表
 * @date 2025/3/13 12:28
 */
public class LeetCode_23 {


    private class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public ListNode mergeKLists(ListNode[] lists) {

        return solution_1(lists,0,lists.length-1);
    }
    
    @Test
    public void test(){
        ListNode list1 = new ListNode(1,new ListNode(4,new ListNode(5,null)));
        ListNode list2 = new ListNode(1,new ListNode(3,new ListNode(4,null)));
        print(merge(list1,list2));
    }

    /**
    * @Description: 分治+两两合并
    * @Author: kunkun
    * @Date:  2025/3/13 12:58
    * @Parameters:
    * @Return
    * @Throws
    */
    private ListNode solution_1(ListNode[] lists,int start,int end) {
        if (start>end){
            return null;
        }
        if (end==start){
            return lists[end];
        }
        int mid = (start+end)/2;
        ListNode head1 = solution_1(lists, start, mid);
        ListNode head2 = solution_1(lists, mid+1, end);
        return merge(head1,head2);
    }

    private void print(ListNode head){
        while (head!=null){
            System.out.print(head.val+" ");
            head=head.next;
        }
        System.out.println();
    }

    private ListNode merge(ListNode list1, ListNode list2) {
        //定义起始指针
        ListNode result = new ListNode(),finalResult = result;
        ListNode left = list1,right = list2;

        //逐个比较
        while (left!=null&& right!=null){
            if (left.val<=right.val){
                result.next=left;
                left=left.next;
            }else {
                result.next=right;
                right=right.next;
            }
            result=result.next;
        }

        //结果合并
        if (left!=null){
            result.next=left;
        }
        if (right!=null){
            result.next=right;
        }
        if (right==null&& left==null){
            result.next=null;
        }
        return finalResult.next;
    }


    /**
    * @Description: 利用堆求解
    * @Author: kunkun
    * @Date:  2025/3/13 12:58
    * @Parameters:
    * @Return
    * @Throws
    */
    private ListNode solution_2(ListNode[] lists){
        ListNode result=new ListNode(),finalResult = result;
        PriorityQueue<ListNode> heap = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        //逐个入堆
        for (ListNode node : lists) {
            if (node!=null){
                heap.add(node);
            }
        }
        //逐个出堆
        while (!heap.isEmpty()){
            ListNode node = heap.remove();
            result.next=node;
            if (node.next!=null){
                heap.add(node.next);
            }
            result=result.next;
        }
        return finalResult.next;


    }






}
